package com.lsa.letcode.the150.evalRpn;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
	static Map<String, Integer> oper2Priority = new HashMap<String, Integer>();
	{
		oper2Priority.put("*", 1);
		oper2Priority.put("/", 1);
		oper2Priority.put("+", 0);
		oper2Priority.put("-", 0);
	}
	
    public int evalRPN(String[] tokens) {
        return -1;
    }
    
    String[] toRPN(String expr) {
    	String[] tokenz = tokenize(expr);
    	
    	List<String> tokenzRpn = new ArrayList<String>();
    	Deque<String> opers = new ArrayDeque<String>();
    	
    	for (String t : tokenz) {
    		Integer priority = oper2Priority.get(t);
    		if (priority != null){
    			while(!opers.isEmpty()) {
    				String oper = opers.peek();
    				if (compareOpers(oper, t) > 0) {
    					tokenzRpn.add(opers.pop());
    					opers.add(t);
    				}
    				else {
    					opers.add(t);
    					break;
    				}
    			}
    		}
    		else if ("(".equals(t)) {
    			opers.add(t);
    		}
    		else if (")".equals(t)) {
    			boolean isPopped = false;
    			while(!opers.isEmpty()) {
    				String oper = opers.pop();
    				if ("(".equals(oper)) {
    					isPopped = true;
    					break;
    				}
    			}
    			if (!isPopped) {
    				throw new RuntimeException("Syntax err");
    			}
    		}
    		else {
    			tokenzRpn.add(t);
    		}
		}
    	
    	return tokenzRpn.toArray(new String[0]);
    }
    
    int compareOpers(String o1, String o2) {
    	Integer p1 = oper2Priority.get(o1);
		Integer p2 = oper2Priority.get(o2);
		p1 = p1 != null? p1 : 10;
		p2 = p2 != null? p2 : 10;
		return p1 - p2;
    }
    
    enum State{
		READY,
		INDIGIT
	};
	
    String[] tokenize(String expr) {
    	List<String> tokenz = new ArrayList<String>();
    	State state = State.READY;
    	StringBuilder current = new StringBuilder();
    	for (int i = 0; i < expr.length(); i++) {
    		char c = expr.charAt(i);
    		if (Character.isWhitespace(c)) {
    			continue;
    		}
    		if (state == State.READY) {
				if (Character.isDigit(c)){
					state = State.INDIGIT;
    				current.append(c);
    			}
				else {
					tokenz.add(String.valueOf(c));
				}
    		}
    		else { // State.INDIGIT
    			if (!Character.isDigit(c)){
					state = State.READY;
					tokenz.add(current.toString());
					current.setLength(0);
					tokenz.add(String.valueOf(c));
    			}
    			else {
    				current.append(c);
    			}
    		}
		}
    	if (state == State.INDIGIT) {
    		tokenz.add(current.toString());
    	}
    	return tokenz.toArray(new String[0]);
    }
}